package main

import "fmt"

// 0-1背包问题
// 我们有一个背包，背包总的承载重量是 Wkg 。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。
// 我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

// i 表示考察到哪个商品了
// cw 当前背包的重量
// items 每个商品的重量
// n 表示物品数量
// w 表示背包的重量
var maxW = -1

func calcBag01(i int, cw int, items []int, n int, w int, targets []bool) {
	if i == n || cw == w {
		if cw > maxW {
			maxW = cw
			fmt.Println("当前背包可装的最大的重量是：", maxW)
			fmt.Println("装背包的配置是：", targets)
			return
		}
	}
	if i >= n {
		return
	}
	// 剪枝
	if cw+items[i] <= w {
		targets[i] = true
		calcBag01(i+1, cw+items[i], items, n, w, targets) // 装进去
	}
	targets[i] = false
	calcBag01(i+1, cw, items, n, w, targets) // 不装进去
}

func main() {
	calcBag01(0, 0, []int{100, 52, 23, 98, 120}, 5, 250, make([]bool, 5))
}
